package com.cskaoyan.javase.recursion._1basic;

import javax.swing.*;

/**
 * 递归的思想
 * 引例：
 * 使用递归计算N（N>=1）的阶乘（factorial）
 * 先使用循环求解一下阶乘问题.
 * 要想使用循环求解,必须找到循环的循环体语句
 * n! = n * (n-1) * (n-2) * ... *1
 *
 * 如果用递归求解,需要找到递归的两要素,递归体以及递归的出口
 * 递归的思想就是分解问题的思想:
 *      1.把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。(递归体)
 *      2.当子问题规模足够小的时候，就可以直接得到小规模问题的解。(递归的出口)
 *      3.然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。
 *
 * n! = n * (n-1)!
 * (n-1)! = (n-1) * (n-2)!
 * (n-2)! = (n-2) * (n-3)!
 * ....
 * 2! = 2
 * 1! = 1
 * 设n的阶乘结果是f(n)
 * 递归的递归体: f(n) = n * f(n-1)
 * 递归的出口: 1! = 1
 *
 * 总结一下递归的优缺点:
 * 优点:
 *      1.递归的分解思想,非常符合人类解决问题的思路
 *          一个问题只要能够找到分解的思路,用递归求解是非常容易的
 *      2.递归的程序,代码往往十分简洁.
 *
 * 缺点:
 *      1.递归求解的过程会涉及大量的重复计算,运算的效率非常低
 *      2.递归求解的过程中会大量占用栈内存空间,十分耗费资源
 *          总之就是"时空复杂度"都不优越.
 *      3.它很危险,容易导致栈溢出错误,会导致程序整个崩溃
 *
 *      综上，递归是一把伤人亦伤己的利器，实际开发中不要随意使用递归，使用递归要深思熟虑递归的深度和出口，避免栈溢出错误
 *
 * @since 11:32
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoopSolution(10));
        System.out.println(factorialRecursionSolution(10));
    }

    public static long factorialRecursionSolution(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorialRecursionSolution(n - 1);
    }

    // 用循环求解n的阶乘
    public static long factorialLoopSolution(int n) {
        // n! = n * (n-1) * (n-2) * ... *1 是n个数相乘,循环的次数就是n次
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}
